package bTree.LeetCode;

import java.util.LinkedList;
import java.util.List;

public class 电话号码的字母组合 {
    List<String> res = new LinkedList<>();
    //定义一个映射
    String[] Strhash = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        StringBuilder sb=new StringBuilder();
        backTracking(sb,digits,0);
        return res;
    }

    private void backTracking(StringBuilder sb, String digits, int index) {
        if (sb.length()==digits.length()){
            res.add(new String(sb));
            return;
        }
        for (int i=index;i<digits.length();i++){
            int i1 = digits.charAt(i) - '0';
            String strhash = Strhash[i1];
            for (int i2 = 0; i2 < strhash.length(); i2++) {
                sb.append(strhash.charAt(i2));
                backTracking(sb,digits,i+1);
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }
}